package data_structure.offer;

import data_structure.tensort.Sort;

import java.util.ArrayList;
import java.util.Arrays;

public class SpecialArrays {

    public static boolean binarySearch(int  []array,int target){
        int left=0;
        int right=array.length-1;
        int mid=0;
        int temp=0;
        array= Sort.quickSort(array, 0, right);//默认采用的是快速排序算法
        while(left<=right){
            mid=(left+right)/2;
            temp=array[mid];
            if(target==temp){
                return true;
            }
            else if(target>temp){
                left = mid+1;
            }
            else if(target<temp){
                right=mid-1;
            }
        }
        return false;
    }
    public static boolean binarySearch(int[][] array, int target) {

        int rows = array.length;
        int columns = array[0].length;
        int length = rows * columns;

        int left = 0;
        int right = length - 1;
        int temp = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            temp = array[mid / columns][mid % columns];
            if (temp == target) {
                return true;
            } else if (temp > mid) {
                left = mid + 1;
            } else if (temp < mid) {
                right = mid - 1;
            }

        }
        return false;
    }

    /**
     * 求一组数组中最小的几个数
     * @param target int[]
     * @param k int k
     * @return ArrayList<Integer>
     */
    public static ArrayList<Integer> getLeastNumber(int []target,int k){
        if(target == null||target.length == 0||k>target.length){
            return null;
        }
        //在temper数组中暂时存放k个元素
        int []temper= Arrays.copyOfRange(target,0,k);
        ArrayList<Integer> result = new ArrayList<Integer> ();
        //构建最大堆
        buildMaxHeap(temper);
        //从target[k]开始，遍历元素，和堆顶元素交换
        for (int i = k; i < target.length; i++) {
            if(temper[0]>target[i]){
                temper[0]=target[i];
                adjustHeap(temper,0);
            }
        }
        for(int i = 0; i < temper.length; i++){
            result.add(temper[i]);
        }
        return result;
    }
    public  static void buildMaxHeap(int []temper){

        for(int i=temper.length/2-1; i >= 0; i--){
            adjustHeap(temper,i);
        }
    }
    public static void adjustHeap(int[] temper, int i){
        int maxIndex=i;
        int left=2*i+1;
        int right = 2 * i+2;

        if(left<temper.length&&temper[left]>temper[maxIndex]){
            maxIndex=left;
        }

        if(right<temper.length&&temper[right]>temper[maxIndex]){
            maxIndex=right;
        }
        if(maxIndex!=i){
            swap(temper,i,maxIndex);
            adjustHeap(temper,maxIndex);
        }
    }
    public static void swap(int []temper,int m,int n){
        int temp=temper[m];
        temper[m] = temper[n];
        temper[n] = temp;
    }
    
}
